In certain programming languages, array data type is implemented using a hashtable. The hashtable is a data structure having “n” number of “slots” of memory. The array elements are stored as key-value pairs in the slots of the hashtable. The index of the array is stored as a key and the element at the index is stored as a value in the hashtable. For example, in an array $arr=array([‘a’]=1), the array element, “1” at an index “a” is stored as a key-value pair (“a,1”) in the hashtable. An element of the array is stored in one of the slots of the hashtable. The particular slot in which the element is stored is determined by hashing the index of the array to a particular slot. The hashing function determines a slot number for a given index.
Prior array implementation techniques have limitations in the way the array elements are stored. Certain implementation techniques do not inherently record or track the order in which the array elements are inserted into the array. So, applications that need to retrieve the elements in the order they were inserted into the array have to include their own logic in the application program to retrieve the elements in the order they were inserted.
Certain prior techniques that support retrieving or tracking the elements in the order they are inserted use pointers. Data is stored into a slot of the hashtable along with, for example, two pointers. One pointer points to the next inserted element and another one points to the previously inserted element. The pointers are updated as and when the elements are added or deleted from the hashtable. Storing pointers with every array element consumes significant memory. Also, reading the chain of pointers to retrieve the elements in the order they are inserted consumes significant processor time.